#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

//递归超时
// class Solution {
// public:
//     bool searchMatrix(vector<vector<int>>& matrix, int target) {

//         return func(matrix,0,0,matrix.size()-1,matrix[0].size()-1,target);

//     }
//     bool func(vector<vector<int>>& matrix,int startrow,int startcol,int endrow,int endcol,int target){
//         if(startrow>endrow||startcol>endcol){
//             return false;
//         }
//         if(matrix[startrow][startcol]>target){
//             return false;
//         }
//         for(int i = startrow;i<=endrow;++i){
//             if(matrix[i][startcol]==target){
//                 return true;
//             }
//         }
//         for(int i = startcol;i<=endcol;++i){
//             if(matrix[startrow][i]==target){
//                 return true;
//             }
//         }
//         return func(matrix,startrow+1,startcol+1,endrow,endcol,target);
//     }
    
// };



class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i = 0;
        while(i<matrix.size()){
            int index;
            if((index = func(matrix[i],target))==-1){
                ++i;
            }
            else{
               return true;
                
            }

        }
        return false;
        
    }
    int func(vector<int>& nums,int target){
        int left = 0;
        int right = nums.size()-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]>target){
                right = mid-1;
            }
            else if(nums[mid]<target){
                left = mid+1;
            }
        }
        return -1;

    }
};

int main(){
    Solution S;
    vector<vector<int>> matrix = {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
    cout<<S.searchMatrix(matrix,19)<<endl;
}
